#ifndef __ALLOCATOR_UTIL__
#define __ALLOCATOR_UTIL__

//returns ceil(log2(v))
//improve this later on for perf
inline int getBinIndex(int v)
{
  int ret = 0;
  while (ret < 32 && (v>>ret))
    {
      ret++;
    }
  if (1<<(ret-1) >= v)
    return ret-1;
  if (1<<ret >= v)
    return ret;
  if (1<<(ret+1) >= v)
    return ret;
  return -1;
}

size_t getBlockSize(void *ptr)
{
  return *(size_t *)ptr;
}

void *getBlockNext(void *ptr)
{
  //return (char *)ptr + 8;
  return *(void**)((char*)ptr + 8);
}

void setBlockSize(void *ptr, size_t val)
{
  *(size_t*)ptr = val;
}

void setBlockNext(void *ptr, void *val)
{
  *(void**)((char*)ptr + 8) = val;
}

//keeps the list sorted by pointers' addresses
//slows everything significantly!
void *insertToList(void **list_head, void *ptr)
{
  if (list_head == NULL)
    {
      *list_head = ptr;
      setBlockNext(ptr, NULL);
      return NULL;
    }
  void *p = *list_head;
  void *prev = NULL;
  void *prevprev = NULL;
  while (p != NULL && p < ptr)
    {
      prevprev = prev;
      prev = p;
      p = getBlockNext(p);
    }
  //now prev < ptr < p
  setBlockNext(ptr, p);
  if (prev == NULL)
    {
      *list_head = ptr;
    } 
  else 
    {
      setBlockNext(prev, ptr);
    }

  //check if it is possible to coalesce
  //check if pair (prev, ptr) makes a continuous block
  if (prev != NULL && ptr != NULL && 
      (((char *)prev + getBlockSize(prev)) == ptr))
    {
      if (prevprev)
	setBlockNext(prevprev, getBlockNext(ptr));
      else
	*list_head = getBlockNext(ptr);
      
      setBlockSize(prev, getBlockSize(prev) * 2);
      setBlockNext(prev, NULL);
      return prev;
    }
  //check if pair (ptr, next(ptr)) makes a continuous block
  void *next = getBlockNext(ptr);
  if (ptr != NULL && next != NULL &&
      (((char *)ptr + getBlockSize(ptr)) == next))
    {
      if (prev)
	setBlockNext(prev, getBlockNext(next));
      else
	*list_head = getBlockNext(next);
      setBlockSize(ptr, getBlockSize(ptr) * 2);
      setBlockNext(ptr, NULL);
      return ptr;
    }

  return NULL;
}

//usually removes from head
void removeFromHead(void **list_head, void *ptr)
{
  if (*list_head == NULL)
    {
      printf("list empty!\n");
      return;
    }
  void *next = getBlockNext(*list_head);
  *list_head = next;
}


#endif //__ALLOCATOR_UTIL__
